
//
// 101210a- AH - Created.
// 101210b- AH - (Hector) Fixed getClosestByMean() bug.
// 101210c- AH - (Hector) Introduced getWithMostKeys and used first in
//               getOptimalMeans.
// 101228 - AH - Minor java doc fix, bug discovered by java doc compiler.
// 111002 - AH - Improved and fixed java doc.
//

package org.soekrat.engine.forest;

import static org.soekrat.engine.util.Util.getRandom;
import static org.soekrat.engine.util.Util.same;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 *   Organizes 
 *   {@link TreeDistanceTable}s for a forest in order to implement Soekrat
 *   forest retrieval strategies.
 * </p>
 * @author Arne Halvorsen (AH)
 * @author Laetitia Le Chatton (LLC)
 */
public final class TreeDistanceTables 
{
  private final Map<String, TreeDistanceTable> m_tables=
    new HashMap<String, TreeDistanceTable>();
  
  private boolean m_closed=false;
  
  /**
   * <p>
   *   Creates empty table.
   * </p>
   */
  public TreeDistanceTables(){}
  
  /**
   * <p>
   *   Tells if {@code this} is closed:
   *   {@link #add(Tree)} will not accept more 
   *   {@link Tree}s. 
   * </p>
   * @return {@code true} if is closed, {@code false} if is not.
   */
  public boolean closed(){ return m_closed; }
  
  /**
   * <p>
   *   Finds the 
   *   {@link TreeDistanceTable} given 
   *   {@link Tree} belongs to (or if table not found, creates table) and adds
   *   it.
   * </p>
   * @param tree {@link Tree} to add.
   * @return {@code this}.
   * @throws IllegalArgumentException If is
   *         {@link #closed() closed}.
   * @throws IllegalArgumentException If found table indexed by {@code tree}'s
   *         root's name is not the tree it belongs to.
   */
  public TreeDistanceTables add(Tree tree)
  {
    if (tree==null)
    {
      throw new NullPointerException("tree");
    }
    
    if (closed())
    {
      throw new IllegalArgumentException("closed");
    }
    
    Tree root=tree.getRoot();
    String name=root.getName();
    TreeDistanceTable tdt=m_tables.get(name);
    if (tdt==null)
    {
      tdt=new TreeDistanceTable();
      m_tables.put(name, tdt);
    }
    else
    {
      if (tdt.getRoot()!=root)
      {
        throw new IllegalArgumentException("table found for name "+name+
          " not for tree given subtree belongs to");
      }
    }
    
    tdt.add(tree);
    
    return this;
  }
  
  /**
   * <p>
   *   Computes the distances for all the tables.
   * </p>
   * <p>
   *   This 
   *   {@link #closed() closes} {@code this}.
   * </p>
   */
  public void compute()
  {
    if (m_closed) return;
    
    for (TreeDistanceTable table : m_tables.values()) table.compute();  

    m_closed=true;
  }
  
  /**
   * <p>
   *   Gets the optimal
   *   {@link Mean}s. 
   * </p>
   * <p>
   *   The optimal means are found as following:
   * </p>
   * <ol>
   *   <li>
   *     Find the means that represents the trees with the lowest mean and 
   *     longest path to root.
   *   </li>
   *   <li>
   *     Among the one found in 1 find the means with trees that has most nodes
   *     matched by keywords.  
   *   </li>
   *   <li>
   *     Among the one found in 2 find the means with minimum mean value.
   *   </li>
   *   <li>
   *     The optimal means are the one among the one found in 3 which represents
   *     the deepest trees.
   *   </li>
   * </ol>
   * @return {@code Mean}s found to be optimal.
   */
  public Mean[] getOptimalMeans()
  {
    if (!m_closed)
    {
      throw new IllegalArgumentException("not closed");
    }
    
    List<Mean> all=new ArrayList<Mean>();
    
    for (TreeDistanceTable table : m_tables.values())
    {
      // Gets the Mean that represents the Tree with the lowest mean and 
      // longest path to root.
      all.add(table.getSmallAndDeep());  
    }
    
    // Gets Means representing the Trees with most keys.
    List<Mean> most=getWithMostKeys(all);
    
    // Finds the minimum means among the ones with most keywords.
    float minMean=getMinMean(most);
    List<Mean> mins=new ArrayList<Mean>();
    for (Mean mean : all)
    {
      if (same(mean.mean, minMean)) mins.add(mean);  
    }
    
    // Finds the deepest trees among the ones with minimum means.
    int maxDepth=getMaxDepth(mins);
    List<Mean> deepest=new ArrayList<Mean>();
    for (Mean mean : mins)
    {
      if (maxDepth==mean.tree.depth()) deepest.add(mean);  
    }
    
    return deepest.toArray(Mean.EMPTY_ARRAY);
  }
  
  /**
   * <p>
   *   Gets the minimum mean values among 
   *   {@link Mean}s.
   * </p>
   * @param means {@link Mean}s.
   * @return Value.
   */
  private static float getMinMean(List<Mean> means)
  {
    float min=Float.POSITIVE_INFINITY;
    for (Mean mean : means)
    {
      if (mean.mean<min) min=mean.mean;   
    }
    return min;
  }
  
  /**
   * <p>
   *   Gets the max depth of 
   *   {@link Mean}'s 
   *   {@link Tree}s.
   * </p>
   * @param means {@code Mean}s.
   * @return Value.
   */
  private static int getMaxDepth(List<Mean> means)
  {
    int max=-1;
    for (Mean mean : means) 
    {
      int d=mean.tree.depth();
      if (d>max) max=d;
    }
    return max;
  }
  
  /**
   * <p>
   *   Gets the closest keys (trees) according to Soekrat retrieval strategy.
   * </p>
   * <p>
   *   Returned is a tree with optimal mean (if there are more than one, one is
   *   selected randomly) and all trees which has a distance from the tree
   *   equal to or less to the optimal mean.
   * </p
   * @return Found.
   */
  public List<Tree> getClosestByMean()
  {
    // Gets optimal means.
    Mean[] means=getOptimalMeans();
    
    // Gets one optimal mean, if there is more than one we choose randomly.
    Mean mean=getRandom(means);
    
    // Gets the tree with the optimal mean and all trees with distances to it
    // equal or less to the found mean.
    return mean.table.getWithDistanceLessOrEqual(mean.idx, mean.mean);
  }
  
  /**
   * <p>
   *   Gets 
   *   {@link Mean}s representing the 
   *   {@link Tree}s with most keys.
   * </p>
   * @param means {@link Mean}s to search.
   * @return Found: All got equal number of keys and are the most.
   */
  private static List<Mean> getWithMostKeys(List<Mean> means)
  {
    int max=getMaxKeyCount(means);
    List<Mean> retVal=new ArrayList<Mean>();
    for (Mean mean : means) if (mean.table.size()==max) retVal.add(mean);
    return retVal;
  }
  
  /**
   * <p>
   *   Gets the maximum number of keys (size of tables).
   * </p>
   * @param means {@link Mean}s to search.
   * @return Count.
   */
  private static int getMaxKeyCount(List<Mean> means)
  {
    int max=0;
    
    for (Mean mean : means) 
    {
      int curr=mean.table.size();
      if (curr>max) max=curr;
    }
    
    return max;
  }
  
}
